#include <iostream>
using namespace std;

class Treap {

public:
        Treap() {
                treap=NULL;
        };
		~Treap() {
			deleteTreap(treap);
		}
		void add(int elem);
		void insert(int pos, int elem);
		void deleteNode(int pos);
		int size();
		void show();
		int sum(int start, int end);



private:

        // структура декартово дерево по неявному ключу
        struct Node {
                int value; // элемент массива, который хрантся в данном узле
                int priority;
                int size; // пазмер узла
                int sum; // сумма значений всех потомков узла дерева и значеняи самого узла
                Node* left; // левый потомок
                Node* right; // правый потомок

                // конструкторы
                Node() : priority(0), size(1), sum(0), left(NULL), right(NULL) {} 
                Node(int v, int p) : value(v), size(1), priority(p), sum(v), left(NULL), right(NULL) {}
                Node(int v, int p, Node* l, Node* r) : value(v), priority(p), left(l), right(r) {
                        size=1;
                        sum=v;
                        if (r!=NULL) {
                                size+=r->size;
                                sum+=r->sum;
                        }
                        if (l!=NULL) {
                                size+=l->size;
                                sum+=l->sum;
                        }                       
                }

        };
        Node* treap; // декартово дерево, в котором будет храниться массив

		void deleteTreap(Node* root); // удаление дерева

		int sizeOf(Node* t); // получение размера

        int sumOf(Node* t);  // получение суммы значений всех узлов дерева


        void updateSize(Node* t); // считает размер
        
        void updateSum(Node* t); // считает сумму
        

        void print(Node* t);

        void split(Node* t, int x, Node** l, Node** r);
        Node* merge(Node* l, Node* r); //слияние двух деревьев
        void insertNode(Node** t, int pos, int elemValue); // вставка элемента на определенную позицию в дереве(то есть слево от него находится pos узлов)
        void remove(Node** t, int pos); // удаляем элемент из определенной позиции
        int sumSegment(Node* t, int start, int end); // сумма на отрезке
};
